COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00014 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a35.tex[154,phy] \today\hfill}
\def\alra{\buildrel a\over\longrightarrow}
\def\elra{\buildrel \epsilon\over\longrightarrow}
\def\Lap{\buildrel L\over\approx}
\def\Lapp{\buildrel L↓1\over\approx}

\bigskip
\line{\bf Semigroups.\hfill}

A semigroup is a set $D$, together with a function $D\times D→D$, usually
written as an infix operator~$\odot$, such that $(u\odot v)\odot w
=u\odot(v\odot w)$. If there is an element $e\in D$, where
$\forall x\;ex=x=xe$, $e$~is called the identity element of the semigroup;
a~semigroup with an identity element is also called a monoid. (``Mono'' $=$
``one''; $e$~is analogous to the number~1). Examples of semigroups:

\smallskip
\disleft 20pt:(1):
The set of $n\times n$ matrices, with matrix multiplication (or addition)
as the operation.

\smallskip
\disleft 20pt:(2):
The set of functions $R→R$, with composition as the operation.

\smallskip
\disleft 20pt:(3):
The set of real numbers, with multiplication (or addition or MAX
or MIN) as the operation.

\smallskip
\disleft 20pt:(4):
The set of strings over $\Sigma$, with concatenation as the operation.

\smallskip
\disleft 20pt:(5):
The set of strings over $\{a,b↓1,b↓2,\ldots,b↓n\}$, where 
$x\odot y=xay$. (This is {\sl not\/} a monoid.)

\smallskip
\disleft 20pt:(6):
The set $\{$true, false$\}$, with $∧$ (or $∨$, or $\oplus$) as the operation.

\smallskip
\disleft 20pt:(7):
Any set, with $x\odot y=x$ (not a monoid).

\smallskip
\disleft 20pt:(8):
The set $\{0,1,2,\ldots,n-1\}$, with $x\odot y=(x+y)\;{\rm MOD}\;n$
(or $(x\times y)\;{\rm MOD}\;n$). 

\smallskip\noindent
A semigroup is finite if its domain is. A finite semigroup can be represented
by its multiplication table.

\smallskip
\disleft 38pt::
{\bf Drill:} Given a finite ``multiplication table'', how can you tell
whether it represents a semigroup? A~monoid?

\bigskip
\line{\bf The semigroup of a language.\hfill}

Let $L$ be any language over alphabet~$\Sigma$. Let $[x]$ be the equivalence
class $\{\,y\mid y\Lap x\,\}$. Define a binary operation~$\odot$
on equivalence classes by $[x]\odot[y]=[xy]$. This operation is well
defined; if we pick different representatives $x'\Lap x$, $y'\Lap y$,
we find $[x']\odot [y']=[x'y']=[xy]$. The operation~$\odot$ is
associative:
$$([x]\odot [y])\odot[z]=[xy]\odot [z]=[(xy)z]
=[x(yz)]=[x]\odot[y\odot z]=[x]\odot([y]\odot[z])\,.$$
It has $[\epsilon]$ as an identity element:
$$[\epsilon]\odot[x]=[\epsilon x]=[x]=[x\epsilon]=[x]\odot [\epsilon]\,.$$
If $L$ is a FAL, $\Lap$ has finite index and the semigroup of~$L$ is
finite, and conversely.

\smallskip
\disleft 38pt::
{\bf Drill:} What is $D$, the domain of the semigroup?

\smallskip
\disleft 38pt::
{\bf Drill:} If $[x]=[y]$, is it necessarily true that $[\widehat{x}]=
[\widehat{y}]$?

\bigskip
A (deterministic, possibly not finite) automaton for any language~$L$ has
start state~$[\epsilon]$, transitions $[x]\alra [xa]$, and accepting
states $[x]\mid x\in L$. (By induction, this automaton is in state~$[x]$
after reading~$x$). The automaton is finite iff $\Lap$ has finite
index iff $L$ is a FAL. A similar automaton for $\widehat{L}$ is the
same except that transitions are
$$[x]\alra [ax]\,.$$

\smallskip
\disleft 38pt::
{\bf Drill:} Show the two automata are well defined.

\bigskip
An automaton (nondeterministic, possibly not finite) for
$C=\{xy\mid yx\in L\,\}$ has start state $\langle 1,[\epsilon],[\epsilon]\rangle$,
transitions
$$\eqalign{\langle 1,[x],[\epsilon]\rangle&\alra\langle 1,[xa],[\epsilon]\rangle
\,,\cr
\langle 1,[x],[\epsilon]\rangle&\elra\langle 2,[x],[\epsilon]\rangle\,,\cr
\langle 2,[x],[y]\rangle&\alra\langle 2,[x],[ya]\rangle\,,\cr}$$
and accepting states
$\langle 2,[x],[y]\rangle\mid yx\in L$.
This automaton is finite if $L$ is a FAL.

\smallskip
\disleft 38pt::
{\bf Drill:} What needs to be shown to complete the proof that $C$ is a FAL
if $L$ is?

\bigskip
An automaton for $\{\,xy\mid y\widehat{x}\in L\,\}$ has initial state
$\langle 1,[\epsilon],[\epsilon]\rangle$, transitions
$$\eqalign{\langle 1,[x],[\epsilon]\rangle&\alra\langle 1,[ax],[\epsilon]\rangle
\,,\cr
\langle 1,[x],[\epsilon]\rangle&\elra\langle 2,[x],[\epsilon]\rangle\,,\quad
\hbox{and}\cr
\langle 2,[x],[y]\rangle&\alra\langle 2,[x],[ya]\rangle\,,\cr}$$
and accepting states $\langle 2,[x],[y]\rangle$ such that $yx\in L$.

Inductive hypothesis: After reading $x$, the automaton can  be in
state $\langle 1,[\widehat{x}],[\epsilon]\rangle$. Also, after reading~$xy$,
it can be in state $\langle 2,[\widehat{x}],[y]\rangle$.

If we have several languages $L↓1$, $L↓2$, etc., let $[x]↓1$ mean
$\{\,y\mid y\Lapp x\,\}$. An automaton for $\fnc{Shuffle}(L↓1,L↓2)$
has initial state $\langle[\epsilon]↓1,[\epsilon]↓2\rangle$,
transitions
$$\eqalign{%
\langle[x]↓1,[y]↓2\rangle&\alra\langle[xa]↓1,[y]↓2\rangle\qquad\hbox{and}\cr
\langle[x]↓1,[y]↓2\rangle&\alra\langle[x]↓1,[ya]↓2\rangle\,,\cr}$$
and accepting states $\langle[x]↓1,[y]↓2\rangle$ such that
$x\in L↓1$, $y\in L↓2$.

\smallskip
\disleft 38pt::
{\bf Drill:} Debug this proof: $P=\{\,x\mid x\,\widehat{x}\in L\,\}$ is
accepted by an automaton with start state~$[\epsilon]$, transitions
$[x]\alra[axa]$, and accepting states~$[x]$ such that $x\,\widehat{x}\in L$.
If $L$ is a FAL, then the above automaton is a~FA, so $P$ is a FAL.

\vfill\eject

Other proofs that $C$, defined above, is a FAL if $L$ is:

\smallskip
\disleft 20pt:(1):
(Using NFA's.) Let $M$ be an NFA for $L$, with one start state~$S$
and one accepting state~$F$, and $Q=\{q↓1,q↓2,\ldots,q↓n\}$. The NFA
below accepts~$C$:

\figbox 3truein:


\smallskip
\disleft 20pt:(2):
(Using infix equivalence.) First consider $\{xay\mid yx\in L\}$, where
$a\not\in\Sigma↓L$. Let a DFA read and store string~$x$, character
by character, replacing the value of~$x$ by a shorter infix-equivalent
string where possible. When it sees `$a$' it reads~$y$ in the same way.
Accepting states are those in  which $yx\in L$, so the language above
is a FAL. By applying to it the GSM mapping which changes $a$ to~$\epsilon$,
we get the desired language as a FAL.

\smallskip
\disleft 20pt:(3):
(Finite semigroups.) Let $L$ have monoid $(D,\odot,e)$, with $D↓+$ the accepted
subset of~$D$. Define a NFA with initial state $\langle 1,e,e\rangle$,
transitions
$$\eqalign{\langle 1,x,e\rangle&\alra\langle 1,x\odot h(a),e\rangle\,,\cr
\langle 1,x,e\rangle&\elra\langle 2,x,e\rangle\,,\cr
\langle 2,x,y\rangle&\alra\langle 2,x,y\odot h(a)\rangle\,,\cr}$$
and accepting states $\langle 2,x,y\rangle$ such that $x\odot y\in D↓+$.



\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft (not published)
December 03, 1984

\bye